#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>

void InsertSort(std::vector<int>& nums)
{
   int n = nums.size();
   for (int i = 1; i < n; ++i)
   {
      int curPoke = nums[i];
      int p = i - 1;
      while (p >= 0 && nums[p] > curPoke)
      {
	 std::swap(nums[p], nums[p + 1]);
	 --p;
      }
      nums[p + 1] = curPoke;
   }
}

void ShellSort(std::vector<int>& nums)
{
   int n = nums.size();
   int gap = n;
   while (gap > 1)
   {
      gap = gap / 3 + 1;
      for (int i = 0; i < n; ++i)
      {
         int end = i - gap;
         int curPoke = nums[i];
         while (end >= 0 && nums[end] > curPoke)
         {
            std::swap(nums[end], nums[end + gap]);
            end -= gap;
         }
         nums[end + gap] = curPoke;
      }
   }
}

void SelectSort(std::vector<int>& nums)
{
   int n = nums.size();
   int left = 0, right = n - 1;
   while (left < right)
   {
      int minI = left, maxI = left;
      for (int i = left; i <= right; ++i)
      {
         minI = nums[i] < nums[minI] ? i : minI;
         maxI = nums[i] > nums[maxI] ? i : maxI;
      }
      std::swap(nums[maxI], nums[right--]);
      std::swap(nums[minI], nums[left++]);
   }
}

void AdjustDown(std::vector<int>& nums, int root, int n)
{
   int parent = root;
   int maxChild = (parent * 2) + 1;
   while (maxChild < n)
   {
      if (maxChild + 1 < n && nums[maxChild + 1] > nums[maxChild]) {
	 maxChild = maxChild + 1;
      }
      if (nums[maxChild] > nums[parent]) {
	 std::swap(nums[maxChild], nums[parent]);
	 parent = maxChild;
	 maxChild = (parent * 2) + 1;
      }
      else {
	 break;
      }
   }
}

void HeapSort(std::vector<int>& nums)
{
   int n = nums.size();
   for (int i = (n - 2) / 2; i >= 0; --i) {
      AdjustDown(nums, i, n);
   }
   int end = n - 1;
   while (end > 0)
   {
      std::swap(nums[0], nums[end]);
      AdjustDown(nums, 0, end);
      --end;
   }
}

void BubbleSort(std::vector<int>& nums)
{
   int n = nums.size();
   for (int i = 0; i < n - 1; ++i)
   {
      bool exchanged = false;
      for (int j = 0; j < n - i - 1; ++j)
      {
	 if (nums[j] > nums[j + 1]) {
	    std::swap(nums[j], nums[j + 1]);
	    exchanged = true;
	 }
      }
      if (!exchanged) { break; }
   }
}

template<class RandomAccessIter>
void Debug(RandomAccessIter first, RandomAccessIter last)
{
   while (first < last)
   {
      std::cout << *first << " ";
      ++first;
   }
   std::cout << std::endl;
}

template<class RandomAccessIter>
RandomAccessIter SortPart(RandomAccessIter left, RandomAccessIter right)
{
   --right;
   RandomAccessIter keyI = left;
   typedef typename std::iterator_traits<RandomAccessIter>::value_type ValueType;
   ValueType key = *left;
   while (left < right)
   {
      while (left < right && *right >= key) {
         --right;
      }
      while (left < right && *left <= key) {
         ++left;
      }
      std::swap(*left, *right);
   }
   std::swap(*keyI, *left);
   return left;
}

template<class RandomAccessIter>
RandomAccessIter SortPartPit(RandomAccessIter left, RandomAccessIter right)
{
   --right;
   RandomAccessIter pitI = left;
   typename std::iterator_traits<RandomAccessIter>::value_type pitVal = *pitI;
   // std::cout  << "pitVal:" << pitVal << std::endl;
   while (left < right)
   {
      while (left < right && (*right) >= pitVal) {
	 --right;
      }
      *pitI = *right;
      pitI = right;
      while (left < right && (*left) <= pitVal) {
	 ++left;
      }
      *pitI = *left;
      pitI = left;
   }
   // std::cout << "pitVal:" << pitVal << std::endl;
   *pitI = pitVal;
   return left;
}


template<class RandomAccessIter>
RandomAccessIter SortPartDoubleIter(RandomAccessIter left, RandomAccessIter right)
{
   RandomAccessIter prev = left, cur = left;
   RandomAccessIter keyI = left;
   typename std::iterator_traits<RandomAccessIter>::value_type key = *keyI;
   while (cur < right)
   {
      if (*cur >= key) { ++cur; }
      else {
	 ++prev;
	 std::swap(*prev, *cur);
	 ++cur;
      }
   }
   std::swap(*prev, *keyI);
   return prev;
}

template<class RandomAccessIter>
RandomAccessIter GetMidIter(RandomAccessIter left, RandomAccessIter right)
{
   typedef typename std::iterator_traits<RandomAccessIter>::value_type ValueType;
   RandomAccessIter midIter = left + (right - left) / 2;
   ValueType maxVal = std::max(*left, std::max(*midIter, *right));
   ValueType minVal = std::min(*left, std::min(*midIter, *right));
   ValueType midVal = *left + *midIter + *right - maxVal - minVal;
   if (*left == midVal) { return left; }
   else if (*midIter == midVal) { return midIter; }
   else { return right; }
}

template<class RandomAccessIter>
std::pair<RandomAccessIter, RandomAccessIter> SortPartThrWays(RandomAccessIter begin, RandomAccessIter end)
{
   RandomAccessIter midI = GetMidIter(begin, end);
   std::swap(*midI, *begin);
   RandomAccessIter left = begin, right = end;
   RandomAccessIter cur = begin;
   typename std::iterator_traits<RandomAccessIter>::value_type key = *begin;
   while (cur <= right)
   {
      if (*cur > key) {
	 std::swap(*cur, *right);
	 --right;
      }
      else if (*cur == key) {
	 ++cur;
      }
      else {
	 std::swap(*cur, *left);
	 ++left; ++cur;
      }
   }
   return std::make_pair(left, right);
}

template<class RandomAccessIter>
void QuickSort(RandomAccessIter first, RandomAccessIter last)
{
   //if (last - first <= 1) { return; }
   //RandomAccessIter mid = SortPartDoubleIter(first, last);
   //// Debug(first, last);
   //// [first, mid) [mid + 1, last)
   //QuickSort(first, mid);
   //QuickSort(mid + 1, last);

   if (last - first <= 1) { return; }
   std::pair<RandomAccessIter, RandomAccessIter> iterPair = SortPartThrWays(first, last - 1);
   // Debug(first, last);
   // [first, left) [left, right] [right + 1, last)
   QuickSort(first, iterPair.first);
   QuickSort(iterPair.second + 1, last);
}

void _MergeSort(int left, int right, std::vector<int>& nums, std::vector<int>& tmp)
{
   if (left >= right) { return; }
   int mid = left + (right - left) / 2;
   // [left, mid] [mid + 1, right]
   _MergeSort(left, mid, nums, tmp);
   _MergeSort(mid + 1, right, nums, tmp);
   //merge
   int begin1 = left, end1 = mid;
   int begin2 = mid + 1, end2 = right;
   int curI = left;
   while (begin1 <= end1 && begin2 <= end2)
   {
      if (nums[begin1] <= nums[begin2]) {
	 tmp[curI++] = nums[begin1++];
      }
      else {
	 tmp[curI++] = nums[begin2++];
      }
   }
   while (begin1 <= end1) {
      tmp[curI++] = nums[begin1++];
   }
   while (begin2 <= end2) {
      tmp[curI++] = nums[begin2++];
   }
   std::copy(tmp.begin() + left, tmp.begin() + right + 1, nums.begin() + left);
}

void MergeSort(std::vector<int>& nums)
{
   int n = nums.size();
   int left = 0, right = n - 1;
   std::vector<int> tmp(n);
   _MergeSort(left, right, nums, tmp);
}

void CountSort(std::vector<int>& nums)
{
   int n = nums.size();
   int minVal = nums[0], maxVal = nums[0];
   for (int i = 0; i < n; ++i) {
      minVal = std::min(minVal, nums[i]);
      maxVal = std::max(maxVal, nums[i]);
   }
   int range = maxVal - minVal + 1;
   std::vector<int> cntMap(range);
   for (int i = 0; i < n; ++i) {
      cntMap[nums[i] - minVal]++;
   }
   int curI = 0;
   for (int i = 0; i < range; ++i)
   {
      while (cntMap[i]--) {
	 nums[curI++] = i + minVal;
      }
   }
}
